package offerbook;

import java.util.Arrays;

/**
 * 有两个排序的数组A1和A2，内存在A1的末尾有足够的空余空间(假设是A2长度的多余空间)容纳A2。
 * 请写一个函数，把A2的所有数字插入A1中，并且所有的数字是排序的。
 * <p>
 * 思路1：对A1从第一个位置开始遍历，若A1小则不动，否则把A2的位置查到A1，把A1所有往后移动。时间O(N²), 空间O(1)
 * 思路2：准备一个辅助数组，进行外排，时间O(N),空间O(N)
 * 思路3：准备三个指针p1,p2,p3分别指向A1的最后一个位置 ，A1的最后一个非0元素位置，A2末尾。
 * 比较p2和p3大小，谁大谁被拿到p1位置。移动p2和p3
 */
public class Code04_BackToPreArr {

    public static void main(String[] args) {
        int[] a1 = new int[]{1, 4, 6, 7, 8, 0, 0, 0, 0};
//        int []a2 = new int[]{3,7,9,11};
        int[] a2 = new int[]{-3, -2, 3, 5};
        System.out.println(Arrays.toString(getRes1(a1, a2)));
        int[] a3 = new int[]{1, 4, 6, 7, 8, 0, 0, 0, 0};
        int[] a4 = new int[]{3, 7, 9, 11};
        System.out.println(Arrays.toString(getRes2(a3, a4)));
        int[] a5 = new int[]{1, 4, 6, 7, 8, 0, 0, 0, 0};
        int[] a6 = new int[]{3, 7, 9, 11};
        System.out.println(Arrays.toString(getRes3(a5, a6)));
    }

    public static int[] getRes1(int[] a1, int[] a2) {
        if (a1 == null || a2 == null) {
            return null;
        }
        int p1 = 0;
        int p2 = 0;
        while (p2 < a2.length && p1 < a1.length) {
            //如果a2当前位置比a1小，那么把a2数插到a1，并且a1所有的往后移动
            if (a2[p2] < a1[p1]) {
                for (int i = a1.length - 1; i != p1; i--) {
                    a1[i] = a1[i - 1];
                }
                a1[p1++] = a2[p2++];
            } else {
                p1++;
            }
        }

        //如果a2没填充完毕，直接把剩下的填充,此时p1 = a1.length
        if (p2 < a2.length) {
            //从后往前填充
            int p3 = a2.length - 1;
            while (p3 >= p2) {
                a1[--p1] = a2[p3--];
            }
        }
        return a1;
    }

    public static int[] getRes2(int[] a1, int[] a2) {
        if (a1 == null || a2 == null) {
            return null;
        }
        /**
         * 要统计出a1最后一个非0元素的位置,根据题意最后全0的长度是a2的长度
         */
        int lastIndex = a1.length - a2.length - 1;

        int[] help = new int[a1.length];
        int index = 0;
        int p1 = 0;
        int p2 = 0;

        while (p2 < a2.length && p1 <= lastIndex) {
            if (a1[p1] < a2[p2]) {
                help[index++] = a1[p1++];
            } else {
                help[index++] = a2[p2++];
            }
        }
        while (p2 < a2.length) {
            help[index++] = a2[p2++];
        }
        while (p1 <= lastIndex) {
            help[index++] = a1[p1++];
        }
        return help;
    }

    public static int[] getRes3(int[] a1, int[] a2) {
        if (a1 == null || a2 == null) {
            return null;
        }
        //a1最后一个位置
        int last = a1.length - 1;
        //a1最后一个非0元素位置
        int p1 = a1.length - a2.length - 1;
        //a2最后一个位置
        int p2 = a2.length - 1;
        while (p1 >= 0 && p2 >= 0) {
            //如果是a2大，则把a2放入最后
            if (a2[p2] > a1[p1]) {
                a1[last--] = a2[p2--];
            } else {
                a1[last--] = a1[p1--];
            }
        }
        //下面两种情况最多 有且仅有1个发生。有一个没有填充完毕
        while (p1 >= 0) {
            a1[last--] = a1[p1--];
        }
        while (p2 >= 0) {
            a1[last--] = a2[p2--];
        }
        return a1;
    }
}
